Hanojské věže

Hanojské věže (Tower of Hanoi) je matematický hlavolam, který vymyslel francouzský matematik Édouard Lucas v roce 1883. Skládá se ze tří kolíků (věží). Na začátku je na jednom z nich nasazeno několik kotoučů různých poloměrů, seřazených od největšího (vespod) po nejmenší (nahoře). Úkolem řešitele je přemístit všechny kotouče na druhou věž (třetí přitom využije jako pomocnou pro dočasné odkládání) podle následujících pravidel:

V jednom tahu lze přemístit jen jeden kotouč.
Jeden tah sestává z vzetí vrchního kotouče z některé věže a jeho položení na vrchol jiné věže.
Je zakázáno položit větší kotouč na menší.

Vypráví se legenda, že někde ve Vietnamu nebo Indii stojí klášter nebo chrám, v němž jsou hanojské věže se 64 zlatými kotouči. Mniši (kněží) každý den v poledne za zvuku zvonů slavnostně přemístí jeden kotouč (v jiných verzích probíhá přemisťování nepřetržitě). V okamžiku, kdy bude přemístěn poslední kotouč, nastane konec světa. Vyřešení tohoto hlavolamu pro 64 kotoučů však vyžaduje 2⁶⁴−1=18 446 744 073 709 551 615 tahů, takže i kdyby mniši stihli provést jeden tah každou sekundu (a postupovali nejkratším možným způsobem), trvalo by jim vyřešení celého hlavolamu přibližně 600 miliard let.

Řešení

Jednoduché řešení

Střídavě se přesunuje nejmenší kotouč a jiný kotouč než nejmenší. Přesunuje-li se nejmenší kotouč, pak se vždy přesune o jednu věž dál ve stále stejném směru, a to doprava při celkovém sudém počtu kotoučů a doleva při lichém (předpokládáme, že věže stojí v řadě vedle sebe, počáteční je nejvíce vlevo a cílová nejvíce vpravo). Je-li již nejmenší kotouč na poslední věži v tomto směru, přesune se na věž na protějším konci. Má-li být přesunut jiný kotouč než nejmenší, je to možné provést vždy jen jediným způsobem. Tímto způsobem lze hlavolam vyřešit na nejmenší možný počet tahů.

Příklad implementace

Následující procedura v programovacím jazyce Pascal vypíše řešení hlavolamu:

procedure Hanoj(n: integer; pocatecni, cilova, odkladaci: char);
begin
    if n>1 then Hanoj(n-1, pocatecni, odkladaci, cilova);
    writeln('Přesuneme kotouč z věže ', pocatecni, ' na věž ', cilova);
    if n>1 then Hanoj(n-1, odkladaci, cilova, pocatecni)
end;

Procedura má čtyři parametry. Prvním je celé číslo označující počet kotoučů, dalšími parametry jsou znaková označení počáteční, cílové a odkládací věže. Například pro tři kotouče a věže označené A (počáteční), B (cílová) a C (odkládací) ji lze zavolat:

Hanoj(3, 'A', 'B', 'C')

a vypíše

Přesuneme kotouč z věže A na věž B
Přesuneme kotouč z věže A na věž C
Přesuneme kotouč z věže B na věž C
Přesuneme kotouč z věže A na věž B
Přesuneme kotouč z věže C na věž A
Přesuneme kotouč z věže C na věž B
Přesuneme kotouč z věže A na věž B

Rekurzívní řešení

Řešení pomocí rekurze vychází z úvahy, že řešení musí obsahovat nejméně jeden tah, v němž je přesunut největší kotouč. Ten však lze přesunout jen tehdy, jsou-li všechny ostatní kotouče nasazeny na třetí věži. Označme počet kotoučů n. Nejprve tedy přesuneme n–1 kotoučů (všechny kromě největšího) na odkládací věž, pak přesuneme největší kotouč z počáteční věže na cílovou a nakonec přesuneme n–1 kotoučů z odkládací věže na cílovou. Přesun n–1 kotoučů ovšem můžeme vykonat pomocí rekurzívního volání tohoto algoritmu pro n–1 kotoučů, protože největší kotouč nám přitom nevadí (na něj můžeme položit jakýkoli jiný, takže můžeme postupovat, jako by nebyl). Přesný postup je tedy následující:

Je-li n>1, pak rekurzívním voláním této procedury přesuneme n–1 kotoučů (tj. všechny kromě největšího) z počáteční věže na odkládací.
Přesuneme největší kotouč z počáteční věže na cílovou.
Je-li n>1, pak rekurzívním voláním této procedury přesuneme n–1 kotoučů z odkládací věže na cílovou.

Z rekurzívního řešení lze dokázat matematickou indukcí, že pro n kotoučů potřebujeme 2ⁿ–1 tahů:

Pro n=1 očividně stačí jediný tah.
Předpokládejme, že pro n–1 kotoučů potřebujeme 2^n–1–1 tahů. Pak pro n kotoučů potřebujeme 2^n–1–1 tahů pro bod 1, jediný tah pro bod 2 a 2^n–1–1 tahů pro bod 3, tedy celkem 2^n–1–1+1+2^n–1–1 = 2ⁿ–1 tahů.

Příklad implementace

V jazyce Python (verze 3):

def moveit(frm, to):
   print (f'Presun {frm} --> {to}')
   
def dohanoi(n, to, frm, using):
   if n == 0: return []
   dohanoi(n-1, using, frm, to);
   moveit(frm, to);
   dohanoi(n-1, to, using, frm);

def main():
   try:
      n = int(input("Zadej pocet kotoucu: "))
      dohanoi(n, 3, 1, 2)
   except ValueError:
      main()
   except RecursionError:
      main()

main()

Výstup:

Zadejte pocet kotoucu
3
Presun 1 --> 3
Presun 1 --> 2
Presun 3 --> 2
Presun 1 --> 3
Presun 2 --> 1
Presun 2 --> 3
Presun 1 --> 3

Rozšíření na čtyři věže

Varianta, v níž jsou čtyři věže namísto tří, se nazývá Reveho hádanka a byla poprvé publikována v roce 1907 v knize Canterburské hádanky (The Canterbury Puzzles) Henryho Dudeneyho.^[1] Na rozdíl od původní varianty není u Reveho hádanky dosud známo optimální řešení ani nejnižší nutný počet kroků pro libovolný počet kotoučů. Algoritmus pro její řešení se nazývá Frame-Stewartův:

Zvolme celé číslo k, které je větší nebo rovno 1 a menší než n.
Přesuneme n–k nejmenších kotoučů z počáteční věže na první odkládací věž rekurzívním voláním tohoto algoritmu.
Přesuneme k zbylých kotoučů z počáteční věže na cílovou pomocí algoritmu pro klasické Hanojské věže, přičemž využijeme jen druhou odkládací věž.
Přesuneme n–k nejmenších kotoučů z první odkládací věže na cílovou rekurzívním voláním tohoto algoritmu.

Tento algoritmus vyžaduje celkem 2^n–k+2^k kroků. Volba k by tedy měla být taková, aby tato hodnota byla nejmenší. Algoritmus je považován za optimální, ačkoli to není dokázáno.

Frame-Stewartův algoritmus lze zobecnit pro libovolný počet věží (označme ho r):

Zvolme celé číslo k, které je větší nebo rovno 1 a menší než n.
Přesuneme n–k nejmenších kotoučů z počáteční věže na r-tou věž rekurzívním voláním tohoto algoritmu.
Přesuneme k zbylých kotoučů z počáteční věže na cílovou s využitím jen r–1 věží rekurzívním voláním tohoto algoritmu. (Je-li r–1=3, pak využijeme klasický algoritmus pro tři Hanojské věže.)
Přesuneme n–k nejmenších kotoučů z r-té věže na cílovou rekurzívním voláním tohoto algoritmu.

Reference

↑ (anglicky) Everything2.com: Reve's Puzzle

Externí odkazy

Obrázky, zvuky či videa k tématu Hanojské věže na Wikimedia Commons

[everything2-1] (anglicky) Everything2.com: Reve's Puzzle

[1]